Wissensbasierte
Systeme INF 5T Wintersemester 2004/2005

Inhaltsverzeichnis

1 Einleitung	3

1.1 Motivation	3

2 Wissensrepräsentation	5

2.1 Produktionsregeln	6

2.2 Klauseln	13

2.3 Constraints	16

2.4 Fuzzy-Logic	20

2.4.1 Operationen auf Fuzzy-Sets	20

2.4.2 Praktische Anwendung:	21

2.5 Neuronale Netze	28

3 Problemlösungsstrategien	37

3.1 Suchverfahren	38

3.2 Planungsverfahren	45

Einleitung

Motivation

Entwicklung von intelligenten Computersystemen mit u.a. folgenden Eigenschaften:

Lernfähigkeit und Flexibilität

Natürlichsprachige Schnittstelle

Lösung komplexer Probleme

Erklärungsfähigkeit

Autonomie

Erforschung von „intelligenem“ Problemlösungsverhalten bei Lebewesen, wie z.B.:

Simulation von Denkprozessen im Gehirn für Rückschlüsse auf die Arbeitsweise des Gehirns

Formalisierung von Expertenwissen für wissensbasierte Systeme erweitert das Expertenwissen

Beispiel: TSP (Travelling Salesman Problem)

Geg.: Verbindungskarte mit Städten

Aufgabe: Mache, ausgehend von Ingolstadt, eine Rundreise durch alle Städte auf dem kürzesten Weg.

Wege (u.a.):	I  A  M  R  N  I oder
I  N  A  R  M  I etc.

Hinweise zum TSP:

Variante des TSP: Knoten können auch mehrfach besucht werden.

Prozeduraler Algorithmus: Berechnung aller Wege durch ineinander geschachtelte Schleifen und Auswahl des kürzesten Weges (vollständige Enumeration).

Komplexität des Problems:
5 Städte: Durchläufe
21 Städte: Durchläufe
n Städte: ⇒ kein Polynom
⇒ non polynomial vollständig (np-vollständig)

Definitionen:

Ein wissensbasiertes System ist ein Computersystem, das das fachliche Wissen von Experten über ein bestimmtes Anwendungsgebiet (Domäne) einsetzt, um Problemstellungen daraus zu lösen. Ein Expertensystem ist ein wissensbasiertes System, das vorwiegend interaktiv genutzt wird. Die Methoden zur Entwicklung wissensbasierter Systeme sind im Forschungsgebiet „Künstliche Intelligenz“ (KI, Artificial Intelligence) zusammengeschlossen.

Zielsetzung:

In dieser Vorlesung werden ausgewählte Grundlagen zu wissensbasierten Systemen vermittelt. Anhand praktischer Anwendungen werden einzelne Themen am Rechner vertieft.

Überblick:

Wissensrepräsentationen

Problemlösungsstrategien

Wissensrepräsentation

Architektur eines wissensbasierten Systems:

Die Wissensrepräsentation ist die Darstellung des Wissens in der Wissensbasis. Jede Wissensrepräsentation verwendet einen speziellen Inferenzmechanismus zur Auswertung des Wissens in der Wissensbasis. Der Inferenzmechanismus wird von der Entwicklungsumgebung bereitgestellt. Dies ermöglicht eine deklarative anstatt einer prozeduralen Beschreibung des Wissens (Was statt Wie). In einem wissensbasierten System sind in der Regel mehrere Wissensrepräsentationen problemspezifisch eingesetzt (hybride Wissensrepräsentation).

Die Erstellung einer Wissensrepräsentation wird von einem Knowledge Engineer im Rahmen einer Wissensaquisition durchgeführt. Hauptproblem dabei ist die Interpretation des informellen Wissens und dessen Formalisierung in einer Wissensrepräsentation (Methoden siehe Literatur).

Zunahme der Deklarivität Wichtigste Formen der Wissensrepräsentation:

objektorientierte Repräsentation

Produktionsregeln (vorwärts verkettete Logik)

Klauseln (rückwärts verkettete Logik)

Constraints

Neuronale Netze

Fuzzy-Regeln (Fuzzy Logic)

Semantische Netze

Semantische Netze sind Entity-Relationship-Modellen sehr ähnlich (siehe Vorlesung Datenbanksysteme). Die objektorientierte Repräsentation ist prozedural ( Grundstudium)

Produktionsregeln

Motivation:

Prozedurales Programm:

Nachteil: Begrenzte Flexibilität

Abhilfe:

Ein Produktionssystem besteht aus:

Produktionsregeln

Datenbasis

Regelinterpreter

Die Datenbasis ist entweder als gewöhnliche Datenstrukturen (Records) oder als Objekte strukturiert. Die Instantiierungen der Datenstrukturen oder der Klassen werden Fakten genannt.

Beispiel: Deklaration eines Faktums der Klasse “Auto”.

Attribute:	Zeichenkette	Autonummer
Zeichenkette	Halter
Integer	Kilometerstand

Instantiierung des Faktums 1 der Klasse Auto:	Autonummer = EI-WZ 123
Halter = Schweiger Claudia
Kilometerstand = 12000 km

Instantiierung des Faktums 2 der Klasse Auto:	Autonummer = EI-EJ 24
Halter = Schweiger Johann
Kilometerstand = 95000 km

Eine Produktionsregel ist ein Sprachkonstrukt der Form:

Die sind Bedingungen über den Daten der Datenbasis des Produktionssystems.
Die sind Aktionen, die die Daten der Datenbasis bearbeiten.

Eine Bedingung kann sich wie in prozeduralen Sprachen üblich auf die Belegung eines Attributs eines Objektes beziehen. Darüber hinaus ist in jeder Bedingung implizit die Prüfung der Existenz der Fakten, die in der Bedingung vorkommen, enthalten. Zugriffsverletzungen sind damit ausgeschlossen.

Beispiel:

Bedingung
impliziert:
Erfüllung der Bedingung für beide Fakten 1 und 2

Die Aktionen erzeugen, modifizieren und löschen die Fakten der Datenbasis.

Beispiel:

Aktion mit ,
,
als Faktum 3.

Die Datenbasis und die Produktionsregeln bilden die Wissensbasis des wissensbasierten Systems. Der Regelinterpreter bildet den Inferenzmechanismus, indem er die Produktionsregeln anhand der Fakten auswertet. Grundlegende Vorgehensweisen sind dabei die Vorwärts- und die Rückwärtsverkettung.

Bei der Vorwärtsverkettung werden die Produktionsregeln durch den Recognize-Act-Cycle interpretiert, der zyklisch eine Produktionsregel auswählt und deren Aktionen ausführt. Der Regelinterpreter kann eine Produktionsregel nur dann auswählen, wenn alle Bedingungen B1, ..., Bn erfüllt sind!

Im allgemeinen sind nicht alle Attribute eines Faktums in den Bedingungen einer Regel eingeschränkt. Die Attribute, die keiner Beschränkung unterliegen, nennt man freie Variablen. Die anderen Variablen bezeichnet man als gebunden. Durch Anwendung einer Regel werden die freien Variablen mit Werten belegt (gebunden). Diesen Vorgang nennt man Unifikation oder Matching. Formale Definition siehe Literatur, z.B. Lloyed.

	R1						
	R2	F1	F5				
	R3						
	R4	F3	F5				
	R5						
	⋮						
	Rn	F6					
F1	F2	F3	F4	F5	F6	...	Fx

Beispiel: Bedingung B1 = Auto.Kilometerstand < 50000

Gebunden: Kilometerstand
frei: Halter, Autonummer

Unifikation mit Faktum1: Halter = Schweiger Claudia; Autonummer = EI-WZ 123
Unifikation mit Faktum2: nicht möglich
Unifikation mit Faktum3: Halter = Schweiger Andreas, Autonummer = EI-HH 10

Jedes Faktum kann für eine Regel mehrfach unifiziert werden. Jede Kombination von Fakten kann für eine Regel nur einmal unifiziert werden. Ansonsten würde der Regelinterpreter in einer Endlosschleife enden. Können mehrere Produktionsregeln unifiziert werden, so wird durch eine Konfliktlösungsstrategie entschieden, welche Regel ausgewählt wird.

Beispiel: Zusätzliche Fakten zu vorherigem Beispiel

Faktum 4: Klasse Stellplatz mit Name S1 und Eigentümer = Schweiger
Faktum 5: Klasse Stellplatz mit Name S2 und Eigentümer = Schweiger

Bedingung: mit:

Unifikationen:
Fakten 1 und 4
Fakten 1 und 5
Fakten 3 und 4
Fakten 3 und 5

Durch die Aktionen ändern sich die Fakten der Datenbasis. Das Ausführen der Aktionen einer Produktionsregel nennt man feuern. Der Recognize-Act-Cycle terminiert, wenn keine Produktionsregel mehr unifiziert werden kann.

Beispiel: Geschäftsszenario

Abkürzungen für die Datenbasis:

Produktionsregeln:

Vorwärts verkettende Regelinterpretation:

Ableitungsbaum:

Bei der Rückwärtsverkettung wird der angestrebte Zielzustand durch revertierte Anwendung der Produktionsregeln auf einen gegebenen Startzustand zurückgeführt.

Beispiel: obiges Geschäftsszenario mit rückwärtsverkettender Regelinterpretation

Kann für einen Zustand der Datenbasis keine Regel gefunden werden (Sackgasse), so wird falls möglich in einen früheren Zustand zurückgesetzt und dort eine andere Regel gewählt. Das Zurücksetzen in den zuletzt gefundenen Zustand nennt man (gewöhnliches) Backtracking. Kann gemäß einer Strategie auch in frühere Zustände zurückgesetzt werden, nennt man dies intelligentes Backtracking.

Beispiel: obiges Geschäftsszenario

Zusätzliche Produktionsregel:

Ableitungsbaum mit gewöhnlichem Backtracking:

Ein Beispiel für ein Produktionssystem ist OPS5. Dieses wurde an der TU München zu MAGSY (Multiagentensystem) (K. Fischer, H. Windisch).

Als Konfliktlösungsstrategien werden in dieser Reihenfolge verwendet:

Einmaligkeit der Unifikation

Neuheit der Fakten

Spezifität der Regel (Anzahl der Bedingungen)

Zufällige Auswahl

<Folie Sprachbeschreibung MAGSY>

Beispiel: Steuerung eines Fahrzeugs zum Ausweichen eines Hindernisses

(literalize Fahrzeug
Name
Geschwindigkeit
Winkel)

(Literalize Hindernis
NameFahrzeug
Richtung
Abstand)

(literalize FahrzeugZustand
NameFahrzeug
Zeitpunkt
Zustand)

(startup (make Fahrzeug ^Name PB2
^Geschwindigkeit -100
^Winkel 178)

(make Fahrzeug ^Name DX1
^Geschwindigkeit 200
^Winkel -45)

(make FahrzeugZustand ^NameFahrzeug PB2
^Zeitpunkt aktuell
^Zustand andocken)

(make FahrzeugZustand ^NameFahrzeug DX1
^Zeitpunkt aktuell
^Zustand reisen)

(make FahrzeugZustand ^NameFahrzeug DX1
^Zeitpunkt Mittagspause
^Zustand laden)
)

Regel, die die Geschwindigkeit des Powerbots anzeigt

(p AusgabePB2Geschwindigkeit
(Fahrzeug ^Name PB2
^Geschwindigkeit <vel>)
--> (write |Powerbot PB2 fährt derzeit mit|)
(write <vel>)
(write |mm/s|)
(write (CRLF))
)

Übung: Geschwindigkeit aller Fahrzeuge ausgeben

p) Ausgabe Geschwindigkeiten

(Fahrzeug ^Name <na>
^Geschwindigkeit <vel>)

--> (write |Fahrzeug | <na> | fährt mit | <vel>)
(write |mm/s| (CRLF))
)

Regel, die die Geschwindigkeiten der Fahrzeuge im aktuellen Zustand reisen auflistet:

(p Reisegeschwindigkeiten
(Fahrzeugzustand ^NameFahrzeug <na>
^Zustand reisen
^Zeitpunkt aktuell)
(Fahrzeug ^Name <na>
^Geschwindigkeit <vel>)
--> (write |Fahrzeug | <na> | reist mit Geschwindigkeit |
<vel> (CRLF))
)

(p AusgabeBewegteFahrzeuge
(FahrzeugZustand ^Zeitpunkt aktuell ^NameFahrzeug <na>
^Zustand <<andocken reisen>>)
--> (write |Fahrzeug | <na> | ist in Bewegung| (CRLF)))

Umfahrung eines Hindernisses

(p R1
(Hindernis ^Abstand < 1000
^Richtung vorne
^NameFahrzeug <na>)
{<fzg> (Fahrzeug ^Name <na>)}
{<zust> (FahrzeugZustand ^NameFahrzeug <na>
^Zeitpunkt aktuell
^Zustand reisen)
--> (modify <fzg> ^Geschwindigkeit 10)
(modify <zust> ^Zustand Kurskorrektur)
)

(p R2
{<fzg> (Fahrzeug ^Name <na> ^Winkel <wi>)}
{<zust> (FahrzeugZustand ^NameFahrzeug <na> ^Zeitpunkt aktuell
^Zustand Kurskorrektur)}
- (Hindernis ^NameFahrzeug <na> ^Abstand < 2000 ^Richtung links)
--> (modify <fzg> ^Winkel (compute <wi> + 90))
(modify <zust> ^Zustand QuerfahrtLinks)
)

(p R3
{<fzg> (Fahrzeug ^Name <na> ^Winkel <wi>)}
{<zust> (FahrzeugZustand ^NameFahrzeug <na> ^Zeitpunkt aktuell
^Zustand Kurskorrektur)}
- (Hindernis ^NameFahrzeug <na> ^Abstand < 2000 ^Richtung rechts)
--> (modify <fzg> ^Winkel (compute <wi> - 90))
(modify <zust> ^Zustand QuerfahrtRechts)
)

(p R4
{<fzg> (Fahrzeug ^Name <na> ^Winkel <wi>)}
{<zust> (FahrzeugZustand ^NameFahrzeug <na> ^Zeitpunkt aktuell
^Zustand QuerfahrtLinks)}
- (Hindernis ^NameFahrzeug <na> ^Abstand < 2000 ^Richtung rechts)
--> (modify <fzg> ^Winkel (compute <wi> - 90))
(modify <zust> ^Zustand Reisen)
)

(p R5
{<fzg> (Fahrzeug ^Name <na> ^Winkel <wi>)}
{<zust> (FahrzeugZustand ^NameFahrzeug <na> ^Zeitpunkt aktuell
^Zustand QuerfahrtRechts)}
- (Hindernis ^NameFahrzeug <na> ^Abstand < 2000 ^Richtung links)
--> (modify <fzg> ^Winkel (compute <wi> + 90))
(modify <zust> ^Zustand Reisen)
)

Regel, die den Abstand und die Richtung des nächsten Hindernisses unter 3 Meter zum Fahrzeug DX1 ausgibt.

(p NaechstesHindernis
(Hindernis ^NameFahrzeug DX1
^Abstand { < 3000 <abst> }
^Richtung <ri>)
- (Hindernis ^NameFahrzeug DX1
^Abstand < <abst>)
--> (write |Richtung nächstes Hindernis | <ri> (CRLF))
)

Klauseln

Eine Klausel ist eine prädikatenlogische Formel erster Ordnung der Form: mit : atomare Formeln und alle Variablen in .

Wird in folgender Notation dargestellt, weil .

Eine atomare Formel ist eine Funktion mit einem booleschen Ergebnis über einer Menge von Variablen .

Klauseln mit werden als Hornklauseln bezeichnet. Klauseln mit und werden Einheitsklauseln genannt und beschreiben Faktenwissen. Eine Klausel mit und heißt Ziel . Eine Klausel mit ist eine leere Klausel .

Beispiel:

ETProf(x) ← IstProf(x), GibtVorlesung(x, GET)	⇒ Hornklausel
⇒ Ziel

Der übliche Inferenzmechanismus für Klauseln ist die Resolution. Sie basiert auf dem Modus Ponens:

Modus Ponens:

Gegeben seien atomare Formeln F und H. Dann gilt:

F	F
H		F	H	∨	¬F
H	H

Beispiel:

F	~ „es regnet“
FH	~ „wenn es regnet, dann ist die Straße naß“
H	~ „die Straße ist naß“

Frage: Ist die Straße naß?	⇒ H∨¬F

Annahme: Die Straße ist nicht naß ⇒ H = false ⇒ ¬F ⇒ es regnet nicht

⇒ Widerspruch, weil es regnet! (F)

Bei der Resolution wird das zu beweisende Theorem negiert und und als Ziel der Faktenmenge hinzugefügt. Durch einzelne Resolutionsschritte wird versucht, einen Widerspruch abzuleiten. Ein Widerspruch liegt vor, wenn die leere Klausel abgeleitet werden konnte. Kann ein Widerspruch abgeleitet werden, ist das Theorem bewiesen.

Die Resulution basiert auf der Technik des Widerspruchsbeweises. Dabei wird eine Annahme bewiesen, indem man die Negation der Annahme durch ein Gegenbeispiel widerlegt.

Beispiel:

Satz: die natürlichen Zahlen besitzen kein Supremum.

Widerpsruchsbeweis: Angenommen es gäbe ein SupremumWiderspruch!!

sup = 1 ist hier ein Gegenbeispiel, das den Widerspruch hervorruft.

Die Belegung der freien Variablen, die beim Widerspruch gebunden wurden, bilden das Ergebnis des Programmlaufs.

Beispiel:

Anfrage an das System: Gibt es einen INF-Professor an der Hochschule?
Ziel:

Unifikation:

Welche zwei Klauseln für einen Resolutionsschritt ausgewählt werden, wird durch eine Suchstrategie festgelegt. Die Resolution ist vollständig, d.h. falls es eine Ableitung der leeren Klausel gibt, wird sie gefunden.

Eine Programmiersprache, in der mit Klauseln programmiert wird, ist Prolog. Die Resolution entspricht der Rückwärtsverkettung von Produktionsregeln. Sackgassen werden durch Backtracking behandelt.

Beispiel (vorheriges Beispiel fortgesetzt):

Anfrage: Ist Schweiger ein INF-Professor?
Ziel:

!! Sackgasse !!

!! Sackgasse !!

Es liegt ein Widerspruch vor, weil die leere Klausel abgeleitet werden konnte. Unifikation: nein, gibt es nicht, weil es keine freie Variable gibt.

Anfrage: Ist Brüdigam ein INF-Professor?
Ziel:

!! Sackgasse !!

!! Sackgasse !!

!! Sackgasse !!

Es liegt kein Widerspruch vor. Also ist Brüdigam kein INF-Professor.

Durch das Sprachkonstrukt cut werden in Prolog Teile des Suchbaumes abgeschnitten. Damit wird zwar an Effizienz gewonnen, aber die Vollständigkeit der Resolution geht verloren.

Eine andere Inferenzmethode für Klauseln stammt aus dem Bereich der deduktiven Datenbanken und basiert auf der Abbildung von Klauseln in Ausdrücke relationaler Algebra. Details siehe Literatur.

Constraints

Motivation

Problemstellungen, in denen freie Variablen so mit Werten belegt werden müssen, daß eine Reihe von Bedingungen erfüllt ist. Praktische Beispiele: Terminplanung, Stundenplanung, Produktionsplanung, Integritätsbedingungen in Datenbanken, autonome, mobile Roboter.

Akademische Beispiele: Kryptoarithmetische Probleme

a)

F H

+ I N

--------

T O P

Lösung, z.B.:

4 1

+ 5 2

--------

0 9 3

b)

S E N D

+ M O R E

------------

M O N E Y

Lösung:

(c) N-Damen-Problem

)

Erforderlich zur Berechnung der Lösung in einem Programmsystem ist die Formalisierung der Aufgabenstellung.

Gegeben seien:

ohne Beschränkung der Allgemeinheit (O.B.d.A.) eine geordnete, nicht-leere Menge von Variablen

eine Grundmenge von möglichen Werten für jede Variable. Die Menge nennt man Domäne von und entspricht dem Datentyp.

Beispiel (SEND + MORE = MONEY):

Ein Constraint ist ein Tupel der Form
mit

ist der Name des Constraints

ist ein Tupel von paarweise verschiedenen Variablen mit . Die Variablen sind entsprechend Var geordnet.

ist die Definition einer Relation

Ein Constraint-Netzwerk ist eine Menge von Constraints.

Beispiel „Send more Money“

Ein Constraint-Problem besteht aus

einem Constraint-Netzwerk C

einer Anfangseinschränkung (initiale Zuweisung) init, die jede Variable vi mit einer Teilmenge ihrer Domäne belegt.

Beispiel „Send more Money“

Eine Einzellösung eines Constraint-Problems ist ein Tupel mit

und

für alle Constraints gilt: d bezogen auf die Variablen in

Die (volle) Lösung eines Constraint-Problems ist definiert als:

Ist die leere Menge, so nennt man CP unerfüllbar, da es keine Einzellösung gibt. ist eine Menge von Tupeln.

Beispiel: ANYCP = ( ANYC, init ANYC )

dann ist

Die Bestimmung der Lösung eines Constraint-Problems ist i.a. np-vollständig. Daher verwendet man zur Lösungsfindung eine zweistufige Vorgehensweise:

Einschränkung des Suchraumes durch lokale Propagierungsmethoden

Suche nach Einzellösungen im Tupel von Mengen

Die Grundidee der lokalen Propagierung ist, jedes Constraint für sich einzeln zu betrachten und die Ergebnisse bzgl. der möglichen Werte der Variablen eines Constraints an andere Constraints, die eine oder mehrere dieser Variablen enthalten, weiter zu geben (zu propagieren). Die Weitergabe wird so lange durchgeführt, bis ein stabiler Zustand erreicht ist.

Das sukzessive Ausschalten von unmöglichen Wertebelegungen liefert für jede Variable eine Menge von übriggebliebenen Werten. Dieses Tupel von Mengen wird nachfolgend als sol-val(CP) bezeichnet. Sol-val(CP) ist nicht vergleichbar mit der Menge von Tupeln sol(CP), weil sol-val(CP) im Gegensatz zu sol(CP) keinerlei Abhängigkeiten zwischen einzelnen Variablen darstellt.

Beispiel: obiges ANYCP

lokale Propagierung:
Betrachtung von constr_2:
Betrachtung von constr_1: ,

Suche:

Darstellungsformen für Constraints

Extensional: Aufzählung aller Tupel
Beispiel:

Prädikativ: Angabe eines Prädikats
Beispiel:

Konstruktiv: Konstruktion der Tupelwerte durch Abbildungen
Beispiel (unidirektional):

Beispiele für Constraint Systeme:

YACSS	TUM

ILOGSolver	ILOG

CPL(R)	IBM (frei)

CHIP	ECRC, COSYTEC

Fordert man, dass die Lösung eines Constraint-Problems alle Constraints erfüllt, so spricht man von harten Constraints. Man kann aber auch Lösungen zulassen, die nicht alle Constraints erfüllen. Dies kann zum Beispiel dann notwendig sein, wenn es keine Einzellösung gibt, die alle Constraints erfüllt. Diejenigen Constraints, auf deren Erfüllung verzichtet wird, nennt man weiche Constraints. Die Aufweichung von harten Constraints zur Bestimmung von Einzellösungen bezeichnet man als Relaxierung von Constraints.

Fuzzy-Logic

Die Relaxierung von harten zu weichen Constraints führt zu einem unscharfen Begriff der „Erfüllung“ eines Constraints (Constraint kann ganz, halb oder auch fast nicht erfüllt sein). Die Fuzzy Logic ermöglicht eine Behandlung unscharfer Begriffe durch Zurückführung auf unscharfe Mengen.

Eine (scharfe) Menge lässt sich wie folgt darstellen:

Gegeben: G Grundmenge von Werten
Dann lässt sich die Menge durch folgende Zugehörigkeitsfunktion charakterisieren

Der Wert 1 der Zugehörigkeitsfunktion zeichnet also einige Elemente aus G aus und markiert damit ihre Zugehörigkeit zu M. Eine unscharfe Menge (Fuzzy Set) lässt sich durch folgende Zugehörigkeitsfunktion herstellen:

Damit kann man gewöhnliche Mengen als spezielle unscharfe Mengen betrachten, bei denen der Bildbereich der Zugehörigkeitsfunktion eingeschränkt ist.

Beispiel: Mercedes-Benz-Händler

Ein Kunde möchte ein Auto kaufen, das weniger als 8 l Kraftstoff auf 100 km verbraucht. Natürlich würde der Kunde den Wagen auch dann kaufen, wenn er 8,1 l auf 100 km verbraucht. Daher ist die Menge der akzeptierten Verbrauchswerte ein Fuzzy-Set wie folgt:

Operationen auf Fuzzy-Sets

Nachfolgend werden Operationen auf Fuzzy Sets o.B.d.A. Für zwei Fuzzy Sets dargestellt.

Mengenoperationen

Gegeben: Fuzzy-Sets

Durchschnitt:

Vereinigung:

Komplement:

Logikoperationen

Gegeben: Fuzzy-Sets

Fuzzy AND:

Fuzzy OR:

ist ein Parameter zur Justierung des Ergebnisses. In beiden Logikoperationen ergibt sich für das arithmetische Mittel. Bei wird das Fuzzy-AND zur Durchschnittsmenge und das Fuzzy-OR zur Vereinigungsmenge.

Praktische Anwendung:

Optimierung

Mit diesen Logikoperationen läßt sich eine Bewertungsfunktion realisieren, die die Fuzzy-Resultate weicher Constraints zu einer Gesamterfüllung aller Constraints zusammenfaßt. Eine Bewertungsfunktion ist eine Funktion, die die Erfüllung einer Menge von in der Regel konkurrierenden Randbedingungen berechnet.

Bei Optimierungsaufgaben bildet jede Randbedingung ein Fuzzy Set. Die Zugehörigkeitsfunktion des Fuzzy-Sets zu einem weichen Constraint gib an, wie die Randbedingung für die betrachtete Alternative (Einzellösung) erfüllt ist. Bei vollständiger Erfüllung liefert die Zugehörigkeitsfunktion des Fuzzy Sets die 1, ansonsten 0. Die Bewertungsfunktion ist in der Regel ein Fuzzy-Logikoperator mit einer bestimmten Justierung.

Beispiel: Routenplanung

Randbedingungen:

R1: Anzahl der Ampeln bis 2 optimal, mehr als 4 Ampeln sind inakzeptabel
R2: Die Wegstrecke ist möglichst kurz und nicht über 100 km.
R3: Die mögliche Durchschnittsgeschwindigkeit liegt über 50 km/h, ist bei 80 km/h optimal und darüber unmöglich (alte Schepperkiste vom Schweiger (Polo))

Gegebene Alternativen:

Berechnung:

Bewertung:

Gleichmäßige Berücksichtigung aller Randbedingungen: Arithmetisches Mittel .

Berücksichtigung der besten Randbedingung: Fuzzy-OR

Berücksichtigung der schlechtesten Randbedingung: Fuzzy-AND

Kombination aus der 1. und 3. Möglichkeit mit

Beispiel: Kreuzungsassistent

Fuzzy-Regler

Prinzip der Regelung

Lösung komplexer Steuerungs- und Regelungsprobleme, für die kein hinreichendes mathematisches Modell existiert.

Eine unscharfe Zahl ist eine unscharfe Menge A auf der Grundmenge ℝ, für die gilt:

Es gibt genau ein

ist stückweise stetig

Beispiel: unscharfe Zahlen

Gegeben: Fuzzy-Set A mit Zugehörigkeitsfunktion :

⇒ beschreibt die unscharfe Zahl 3.

Gegeben: Fuzzy-Set mit

⇒ beschreibt die (scharfe) Zahl 3.

Auch Menschen benutzen gerne unscharfe Formulierungen. Diese werden mit linguistischen Variablen und linguistischen Werten modelliert.

Beispiel: Linguistische Variable „Helligkeit“

Reglerbeschreibung:

Programmierung des Reglers durch Produktionsregeln, in denen unter Umständen auch Disjunktionen zugelassen sind.

Die Bedingungen beziehen sich auf die Sensordaten.

Die Aktionen sind Vorgaben an die Aktoren.

Verwendung linguistischer Variablen und Werte auf beiden Seiten der Regel.

Beispiel:

if (Geschwindigkeit = hoch AND Abstand = gering) then Geschwindigkeit = niedrig

Inferenzmechanismus

Um ein Schwingen des Regelkreises zu vermeiden, werden die Aktionen aller Produktionsregeln, die in einem Zyklus unifiziert wurden, zusammengefaßt. Der Bedingungsteil einer Fuzzy-Regel ist im Allgemeinen nicht vollständig erfüllt. Daher ist auch die vollständige Ausführung der Regel generell nicht sinnvoll. Stattdessen ist die Ausführung entsprechend dem Erfüllungsgrad der Bedingungen angebracht. Der Erfüllungsgrad kann z.B. mit der Min-Max-Inferenz-Methode bestimmt werden. <siehe Folie Beispiel 8.3>

Fuzzifizierung der Meßwerte der Sensoren

Bestimmung der Überdeckung der Fuzzy-Sets der Meßwerte mit dem Fuzzy-Set der linguistischen Variablen

logische Verknüpfung der Einzelbedingungen und „Abschneiden“ der Fuzzy-Sets der Stellgröße

Vereinigung der „abgeschnittenen“ Fuzzy-Sets

Transformation des resultierenden Fuzzy-Sets in einen scharfen Wert (Defuzzifikation)

Wichtige Methoden zur Defuzzifikation:

Bildung des Mittelwerts aller Maxima

Auswahl eines Maximums, z.B. von links nach rechts

Schwerpunktbildung: , ,

<siehe Handout>

Neuronale Netze

Die neuronalen Netze sind eine Wissensrepräsentation, die nach dem Vorbild des menschlichen Gehirns arbeitet. Sie versucht in Struktur und Funktionsweise Gehirnkomplexe nachzubilden, um dadurch eine Simulation menschlicher Denkvorgänge zu erreichen.

Aufbau des menschlichen Gehirns:

Es besteht aus mehr als 100 Milliarden Nervenzellen, sogenannter Neuronen.

Der Zellkörper ist der Informationsträger. Die Information wird als Grad der Erregung der Zelle gespeichert. Im einfachsten Fall sind dies die beiden Zustände erregt und nicht erregt. Das Neuron gibt seine Erregung über Axone an andere Nervenzellen und Körperteile (Muskeln etc.) weiter. Ein Axon kann bis zu 1,5 m lang sein. Die Reize gelangen über die Dendriten in das Neuron. Am Ende einer Dendrite sitzt eine Synapse, ein Anschluss zu einem Axon einer anderen Zelle. Über die Synapsen können Erregungszustände verstärkt oder gedämpft an andere Neuronen weitergegeben werden. Überschreitet das weitergegebene Erregungssignal die Reizschwelle der verbundenen Nervenzelle (ca. 70 mV), so verändert diese Nervenzelle die eigene Erregung.

Die Eingabe von Information in das Gehirn erfolgt durch Reize, die durch Rezeptoren hervorgerufen werden. Zur Ausgabe dienen die Effektoren.

Aufbau neuronaler Netze

Ein neuronales Netz besteht aus einer Menge von Prozessoren (Neuronen), die in Form einer Hierarchie miteinander verschaltet sind. Die Anzahl und die Verschaltung der Neuronen ist anwendungsspezifisch, z.B. Perzeptron, Kohonen-Netz. Das hierarchische Netz ist in Eingabeschicht, verborgene Schicht und Ausgabeschicht unterteilt.

Der Informationsfluss erfolgt von der Eingabeschicht über die verborgene Schicht zur Ausgabeschicht oder umgekehrt. Jedes Neuron besitzt eine Menge von Ein- und Ausgängen. Jedes Eingangssignal wird mit einem Faktor gewichtet. Die Verknüpfung der gewichteten Eingangssignale ruft im Neuron eine Aktivierung hervor, falls das Ergebnis der Verknüpfung einen Schwellwert überschreitet. Diese Aktivierung wird über die Ausgänge an andere Neuronen weitergegeben.

Funktionen eines Neurons

Seien die Ausgangsaktivierung des Neurons , die Gewichtung der Verbindung zwischen den Neuronen und .

Propagierungsfunktion:

Aktivierungsfunktion:

Ausgangsfunktion:

Gängige Aktivierungsfunktionen beschränken sich auf als Parameter. Die wichtigsten Aktivierungsfunktionen sind:

Die Ausgabefunktion schaltet in der Regel den Aktivierungszustand ohne Veränderung weiter.

Damit ist die Hauptanwendung von neuronalen Netzen die Erkennung von Mustern. Die Aktivierung von Neuronen der Eingabeschicht von außen ruft die Aktivierung von Neuronen der Ausgabeschicht hervor. Ein derartiger Betrieb des neuronalen Netzes nennt man Recall-Phase.

Damit das neuronale Netz aus dem Eingabemuster das richtige Ausgabemuster erzeugt, muss es in einer Trainingsphase die Mustererkennung erlernen. Das Lernen erfolgt durch Veränderung der Gewichte der Verbindungen.

Das Lernen kann nach verschiedenen Lernregeln erfolgen:

Delta-Regel: Lernregel für zweischichtige Netze

mit:

Ziel (gewünschter Output) des Neurons

Fehlersignal des Neurons

Lernrate

Die Lernrate bestimmt die Größe der Lernschritts. Für wird nicht gelernt. Ist , dann werden die Gewichte, die schon vorher erlernte Muster erkennen konnten, wahrscheinlich verdrängt. Das Netzwerk merkt sich das Muster so stark, dass die alten Muster unter Umständen nicht mehr erkannt werden.

Wird für ein Eingabemuster kein passendes Ausgabemuster erzeugt, so wird die Differenz zwischen Soll- und Istausgang bestimmt. Danach speist man die Differenz über die Ausgabe in das Netz ein und korrigiert die Gewichte. Dadurch ergibt sich bei der nächsten Erkennung ein Ausgabemuster, das näher am Sollwert liegt. Recall- und Trainingsphase wechseln sich ab.

Beispiel: Training eines neuronalen Netzes

Aktivierungsfunktion:

Initiale Gewichte:

Lernrate:

Recall-Phase

Eingabemuster:
Sollausgabemuster: ,

Istausgabemuster:

1. Trainings-Phase

⇒

⇒

⇒

2. Recall-Phase

⇒

⇒

⇒ n.i.O

2. Trainingsphase

⇒

3. Recall-Phase

⇒

⇒

⇒

4. Recall-Phase

⇒

⇒

⇒

⇒ Sollausgabemuster

Die Delta-Regel ist nur für zweischichtige Netze anwendbar. Durch Prüfung der linearen Trennbarkeit kann festgestellt werden, ob ein Problem durch ein zweistufiges Netz gelöst werden kann. Dabei werden die Sollausgaben in ein Koordinatensystem eingetragen. Die Sollausgaben sind linear trennbar, wenn jede mögliche Lösung nur in einer zusammenhängenden Fläche vorkommt.

Ein weiteres Lernverfahren für zweischichtige Netze ist die Hepp'sche Regel. Diese besagt: Falls zwei Neuronen gleichzeitig aktiv sind, dann wächst die Stärke ihrer Verbindung. Sie läßt sich besonders gut bei Problemen mit orthogonalen Eingabevektoren anwenden.

Beispiel: Logisches UND

Lernrate:

Initiale Gewichte:

Aktivierungsfunktion: Treppenfunktion mit

Prüfungsfunktion lineare Trennbarkeit:

Bestimmung Lernregel: Bis auf Eingabevektor orthogonal  Versuch Hebb'sche Regel

Lernen von Muster 4:

n.i.O:

Ein Lernverfahren, das die verborgene Schicht einschließt, ist das Backpropagation-Lernverfahren.

Backpropagation-Algorithmus

Gegeben: Neuronales Netz mit verborgener Schicht

Eingabemuster

Sollausgabemuster

Istausgabemuster

Dann berechnet sich der quadratische Fehler wie folgt:

Der Faktor ist zur Vereinfachung der Formeln zur Berechnung der Gewichte. Die Änderung der Gewichte berechnet sich wie folgt:

Der Differentialquotient wird über die Kettenregel gebildet.

Fehlersignal für das Neuron :

Daraus folgt:

(Delta-Regel für zweistufige Netze)

Für den Backpropagation-Algorithmus wird eine signoide Aktivierungsfunktion gewählt:

mit Identität als Ausgabefunktion:

für die Neuronen der Ausgabeschicht

für die Neuronen der inneren Schichten

Beispiel: Signoide Funktion

Eingabemuster:

Ausgabemuster:

Lernrate:

Initiale Gewichte:

Aktivierungsfunktion:
1. Recall-Phase:

⇒

⇒

1. Trainings-Phase:

2. Recall-Phase

52. Trainings-Phase

52. Recall-Phase

90. Trainings-Phase

91. Recall-Phase

Erhöhung der Lernrate auf bringt Verkürzung auf 44 Trainingsphasen.

Die bisher behandelten Netze sind Feedforward-Netze, weil bei der Recall-Phase keine Zyklen auftreten. Feedback-Netze beinhalten Rückkoppelungen. Die Recall-Phase terminiert dann, sobald ein stabiler Erregungszustand bei allen Neuronen erreicht ist. Ein bekannter Vertreter der Feedback-Netze sind die Hopfield-Netze. Sie werden zur Mustererkennung bei SW-Bildern eingesetzt. Der Physiker Hopfield beschäftigte sich mit dem Verhalten von Spingläsern. Daraus hat er die Theorie der Hopfield abgeleitet.

⇒

Hinweis: die Verdrahtung der einzelnen Neuronen erfolgt auf alle anderen Knoten bis auf sich selbst!

Aktivierungsfunktion:
ist in der Regel gleich .

Energiefunktion:

Abbildung des Hopfield-Netzes in eine Matrix, so daß gilt:

ein erkanntes Muster, Matrix des Netzes ⇒ .

Wenn für Vektoren Matrizen für die Hopfield-Netze berechnet wurden, dann gilt:

erkennt die Muster .

Für Netze mit einigen hundert Neuronen gilt:

mit Anzahl speicherbarer Muster, Anzahl der Neuronen.

Beispiel: Hopfield-Netz für die Muster

Beispiel: Erkennung von gestörten Mustern

  

 

    ...

Jedem gelernten Muster entspricht einem Energieminimum.

Umgehen lokaler Minima durch Simulated Annealing.

Problemlösungsstrategien

Man unterscheidet zwei Klassen von Problemlösungsstrategien:

allgemeine Strategien
einheitliche Vorgehensweisen, die für verschiedene Probleme anwendbar sind
Vorteile: Standardisierung und Übertragbarkeit
Betrachteter Vertreter: Suchverfahren

problemspezifische Strategien:
Vorgehensweisen, die in der Regel aus einer allgemeinen Strategie abgeleitet und auf spezielle Problemklassen zugeschnitten wurden.
Vorteil: Höhere Leistungsfähigkeit innerhalb der Problemklasse.
Betrachteter Vertreter: Planungsverfahren.

Suchverfahren

Szenario: Wegesuche

S	Startpunkt
Z	Zielpunkt

Die Wegsuche läßt sich als Suche im zugehörigen Graphen beschreiben.

Sichtbarkeitsgraph:

Für die Lösung kommen in dieser Vorlesung nur Pfade ohne Zyklen in Frage. Dies ist im Allgemeinen nicht so.

Suchbaum:

Der Suchbaum steht für ein gegebenes Problem vorab im Allgemeinen nicht zur Verfügung, sondern wird im Zuge der Wegsuche aufgebaut. Der Aufbau des Suchbaumes kann nach verschiedenen Verfahren erfolgen. Die wichtigsten Verfahren werden nachfolgend betrachtet.

Breitensuche

Der Suchbaum wird schichtenweise aufgebaut, d.h. es werden stets alle Nachfolger zu Knoten einer Schicht erzeugt, bevor in die nächste Schicht gewechselt wird. Die erste Schicht besteht nur aus dem Startknoten.
Prozedur Breitensuche
Eingabe: Graph G, Startknoten S, Zielknoten Z

Initialisiere Liste L mit S

Solange Ende noch nicht erreicht, wiederhole

Setze P als erstes Element von L

Prüfe, ob P gleich Z ist
Falls ja, Ende.

Lösche erstes Element in L

Strategische Aktionen

Füge alle Nachbarn von P in G ans Ende von L

lösche diejenigen neuen Knoten, die Pfade mit Zyklen ergeben

Beispiel: Listenentwicklung für Breitensuche

Listenentwicklung:	Suchbaum:

S
AD
DBD
BAE
ECE
CBF
F
Z

Die Breitensuche ist vollständig.

Tiefensuche:

Bei der Tiefensuche wird ein expantierter Knoten sofort weiter expandiert. Bei Sackgassen wird durch Backtracking in frühere expandierte Knoten zurückgesetzt.
Prozedur Tiefensuche
Eingabe: Graph G, Startknoten S, Zielknoten Z

füge alle Nachbarn von P in G an den Anfang von L

lösche alle neuen Knoten, die Pfade mit Zyklen darstellen

Beispiel: Listenentwicklung für Tiefensuche + <Grafik 3>

S
AD
BDD
CED
ED
BFD
ZD

Mit chronologischem Backtracking ist die Suche vollständig.

Die beiden Verfahren Breiten- und Tiefensuche unterscheiden sich in der Reihenfolge, in der die Knoten des Suchbaums expandiert werden. Diese lässt sich durch Hinzunahme von Wissen über die Wegpunkte (Heuristiken) verbessern.

Gradientenmethode (Hill-Climbing)

Diese Methode befolgt die einfache Heuristik:

„Nimm den Knoten, der dich dem Ziel am nächsten bringt“.

Falls eine Abstandsfunktion für Stellungen definiert ist, kann diese Heuristik wie folgt formalisiert werden:

„Gehe von zu , falls minimal unter den Nachfolgern von ist.“

Strategische Aktionen:

Füge alle Nachbarn von P an den Anfang von L. Sortiere die neuen Knoten nach dem genschätzen Abstand zum Ziel.

Lösche alle neuen Knoten, die Pfade mit Schleifen darstellen.

Problem: Es kann vorkommen, dass nach der Abstandsfunktion lokal bestimmte Nachfolger weiter vom Ziel entfernt sind als Knoten, die bereits früher expandiert wurden. Eine Verbesserung stellt die „Best-First-Suche“ dar.

Best-First-Suche

Dieses Verfahren arbeitet analog zum Hill-Climbing. Die Sortierung erfolgt jedoch über die gesamte Liste.

Strategische Aktionen:

Füge alle Nachbarn von P in L ein. Sortiere alle Knoten in L nach dem geschätzten Abstand zum Ziel.

Lösche die (neuen) Knoten, die Pfade mit Schleifen bilden.

Bidirektionale Suche

Die bisherigen Suchverfahren gehen von einem Startknoten zu einem Zielknoten. Lässt man dynamisch mehrere Start- und Zielknoten zu, so kann parallel ausgehend von den jeweiligen Start- und Zielknoten mit Breitensuche gesucht werden. Die Suche terminiert, sobald ein expandierter Knoten einem Startpunkt des entgegen gerichteten Suchlaufs entspricht.
Das Verfahren wird sehr häufig in Kombination mit der Strahlensuche verwendet. Die Strahlensuche expandiert die Knoten einer Ebene entsprechend der Breitensuche. Danach wird die Menge der expandierten Knoten über eine Heuristik auf eine sinnvolle Anzahl von Knoten reduziert. Diese werden erneut expandiert.

Beispiel: Bidirektionale Strahlensuche mit Abstand als Kantengewicht und der Breite 2

Suche über Nadelöhrmengen

Je nach Problemstellung kann es im Graphen Knotenmengen geben, die in vielen Lösungen enthalten sind. Diese Knoten sind daher neuralgische Punkte oder Engstellen, durch die der gesuchte Weg mit großer Wahrscheinlichkeit führt. Diese Knoten nennt man Nadelöhrmenge.

Beispiel:

Donaubrücken sind Nadelöhre in Ingolstadt

Lässt sich bei einem Problem eine Nadelöhrmenge finden, so liegt es nahe, die Suche zu parallelisieren. Es wird z.B. bidirektional vom Startknoten zur Nadelöhrmenge und vom Ziel zur Nadelöhrmenge gesucht.

Beispiel:

Die Menge ist eine Nadelöhrmenge.

Übersicht

Optimierende Suchverfahren

Während bisher die grundsätzliche Erreichbarkeit des Zielknotens im Vordergrund stand, sollen nun beste Wege gesucht werden. Dazu betrachten wir Graphen, bei denen jeder Kante ein Gewicht zugeordnet ist. Das Gewicht einer Kante entsteht durch eine Kostenfunktion. Ein Weg von nach ist optimal, wenn für ihn die niedrigsten Gesamtkosten entstehen.

A*-Algorithmus

Für die Bewertung eines Wegpunktes Y als Nachfolger des Wegpunktes X werden stehen folgende Funktionen zur Verfügung:

Liegt auf dem besten Weg vom Startknoten zum Zielknoten und ist exakt, dann ist gleich der Kosten des besten Weges vom Start- zum Zielknoten. Für einen Nachfolger von , der vom besten Weg abweicht, gilt: . Damit ist der Weg von über suboptimal.

Strategische Aktionen:

Expandierung von liefert

Berechne für
Füge in ein
Sortiere nach

Lösche neue Knoten aus , die im Suchbaum schon vorher aufgetreten sind, falls vorheriger Knoten einen niedrigeren -Wert hat.
Ansonsten lösche Nachfolger des vorherigen Knotens und lösche vorherigen Knoten.

Die Aktualisierung der Nachfolger eines gelöschten Knotens ist notwendig, falls dieser bereits expandiert wurde.

Beispiel: A*-Algorithmus

Listenentwicklung	Suchbaum

S

A B

C B ~> B C

C C ~> C

D

E

Z

Eine Funktion zur Bewertung eines Knotens heißt zulässig, wenn sie die Kosten, um zum Ziel zu kommen, nicht überschätzt. Für jeden Knoten und jeden Zielknoten , der von aus erreicbar ist, gilt: . Ist die Funktion zulässig, so liefert der A*-Algorithmus für das Problem eine optimale Lösung. Für praxisrelevante Problemstellungen ist es oft schwierig, eine zulässige Schätzfunktion zu finden. Daher läßt man diese Forderung im Hinblick auf eine Effizienzsteigerung bei der Suche gelegentlich fallen. Der A*-Algorithmus schließt Mehrfachwege zu einem Knoten aus und reduziert damit den Suchraum.

Planungsverfahren

Die Problemklasse der Planungsprobleme ist in der Technik sehr verbreitet. Beispiele für Planungsprobleme sind

Konfigurieren

Ressourcenplanung

Aktionsplanung

Trajektorienplanung bei Robotern

Ein Konfigurationsproblem KP ist ein Tupel der Form:
mit	B:	Bauteilmenge
R:	Randbedingungsmenge für B
G:	Bewertungsfunktion für R
A:	Aggregation von B nach O mit O zusammengesetztes Objekt
F:	Anforderung für O mit
RF:	Menge der Randbedingungen für O
GF:	Bewertungsfunktion für RF
HF:	Mindestbewertung für GF
H:	Mindestbewertung für F

Die Aggregation A simuliert das Zusammensetzen der gewählten Bauteile aus B zu einem konfigurierten Objekt O. Die Aggregation projeziert beim Zusammensetzen die Eigenschaften der Bauteile aus B in Eigenschaften der Objekte O. Dies ist nötig, weil der Auftraggeber für die Konfigurierung in der Regel nur die Eigenschaften des zusammengesetzten Objekts kennt und nur darüber seine Randbedingungen formulieren kann. Die Eigenschaften der Bauteile will der Auftraggeber in der Regel auch nicht kennen.

Beispiel: Konfigurieren eines Ladeportals

B	Menge aller Typen von Kragstützen, Führungsträgern, Laufwägen und	Hubeinheiten

R	Menge aller technischen Restriktionen (Bremsweg des Laufwagens, Traglast	der Hubeinheit

R	Das Ladeportal ist mit den vorhandenen Lagerbeständen produzierbar und	etabliert einen neuen Laufwagen im Markt

A	Abbildung der Bauteileigenschaften in Eigenschaften des Portals (Gesamt-	preis, Wartungsintervall)

GF	Das Portal ist hochwertig und kostengünstig

RF	Kundenrestriktion für Preis, Lieferzeit, Wartungsintervall

H, HF	Mindestqualitätsmaße, ab der der Kunde das Portal kauft

Geeignete Wissenrepräsentationen für Konfigurationsprobleme sind Constraints in Verbindung mit Produktionsregeln.

Planungsprobleme unterscheiden sich von Konfigurationsproblemen in der zeitlichen Anordnung der gewählten Objekte im Plan. Der Plan besteht aus einer Liste von Aktionen.

STRIPS

Anwendung der Suchverfahren zur Planung in STRIPS (Standford Research Institute Problem Solver). STRIPS wird nachfolgend anhand der Blocksworld erklärt.

Die Suche erfolgt im Zustandsraum. Jeder Zustand ist beschrieben durch eine Menge von Merkmalen.

Zustand S	Zustand Z

Jeder Zustand ist durch eine Menge von Merkmalen folgender Prädikate beschrieben:

On (x, y)	Klotz x liegt auf Klotz y
Clear (x)	Auf Klotz x liegt kein anderer Klotz
Table (x)	Klotz x liegt auf dem Tisch

Das Planungsproblem ist in STRIPS gegeben durch einen Ausgangs- und einen Zielzustand. Der Übergang von einem Zustand in einen anderen erfolgt durch Anwendung von Aktionen (Operatoren). In der Blocksworld sind folgende Operatoren verfügbar:

move (x, y, z)	Bewege x von y auf z
unstack (x, y)	Nimm x von y und lege ihn auf den Tisch
stack (x, y)	Hebe x vom Tisch und lege ihn auf y

Der Übergang von einem Zustand kann durch beliebige Anwendung von Operatoren erfolgen. In jedem Operator ist durch eine Vorbedingung festgelegt, in welchen Fällen er angewendet werden kann. Die Nachbedingung eines Operators legt fest, welche Merkmale des Zustands neu hinzukommen und welche nicht mehr gelten.

Beispiel: move (x, y, z)

Vorbedingungen: Clear (z), Clear (x), On (x, y)

Nachbedingungen:
Hinzu: On (x, z), Clear (y)
Weg: Clear (z), On (x, y)

Die Problemlösung erfolgt nach den bekannten Suchverfahren.

Beispiel:

Übergang von obigem Zustand S zu Z:

unstack (C, A)
stack (B, C)
stack (A, B)

Potentialfeldmethode

Anwendung bei Wegplanung für mobile Roboter: Die Lage eines zylindrischen Roboters wird durch eine Konfiguration p = (x, y) beschrieben. Die Kraft auf den Roboter ist der Gradient des Potentialfeldes u(p):

Der Roboter bewegt sich nach der Methode des steilsten Abstiegs auf das Ziel zu. Der Zielpunkt erhält ein anziehendes Potential. Durch abstoßendes Potential der Hindernisse wird ein größtmöglicher Abstand von den Hindernissen erreicht.

Sei:

Möglische Definition des Potentials als

anziehendes Potential:

Abstoßendes Potential:

mit	Gewichtungsfaktor
Gewählte Potentialhöhe in den Hindernissen

Gesamtpotential:

Durch trichterförmige Verkleinerung des anzuziehenden Potentials wird die Planung effizienter.

Stichwortverzeichnis

Aktionen	7

Anfangseinschränkung	17

arithmetisches Mittel	21

Axon	28

Backpropagation-Lernverfahren	32

Backtracking	10

Bedingung	6

Bewertungsfunktion	21

Constraint-Netzwerk	17

Constraint-Problem	17

Datenbasis	6

Definition des Potentials	48

deklarative Beschreibung	5

Delta-Regel	29

Dendriten	28

Domäne	4, 16

Effektoren	28

Einheitsklauseln2	13

Einzellösung	17

erregter Zustand	28

Existenz	6

Expertensystem	4

Extensional	18

Feedback-Netze	34

Feedforward-Netze	34

Formalisierung	16

freie Variable	7

Fuzzy Set	20

gebundene Variable	7

Gewichte	29

Grundmenge	16

harte Constraints	19

Hepp'sche Regel	31

Heuristiken	41

Hopfield-Netze	34

Hornklauseln1	13

Inferenzmechanismus	5, 13

intelligentes Computersystem	3

Klausel	13

Knowledge Engineer	5

Konfliktlösungsstrategie	8

Konstruktiv	18

Kostenfunktion	44

Künstliche Intelligenz	4

leere Klausel	13

linguistische Variablen	25

Liste von Aktionen	47

Matching	7

Menge von Tupeln	17

Merkmale	47

Min-Max-Inferenz-Methode	26

Modus Ponens	13

Mustererkennung	29

Nachbedingung	48

Nadelöhrmenge	43

Name	17

Neuronen	28

Operatoren	48

Prädikativ	18

Produktionsregel	6

Produktionssystem	6

propagieren	18

Recall-Phase	29

Reizschwelle	28

Relation	17

Relaxierung	19

Resolution	13

Rezeptoren	28

Sackgasse	10

Simulated Annealing	36

STRIPS	47

Synapse	28

Tupel von Mengen	18

Unifikation	7

unscharfe Menge	20

unscharfe Zahl	25

Variablen	16f.

vollständige Enumeration	4

Vorbedingung	48

Vorwärtsverkettung	7

weiche Constraints	19

Wissensaquisition	5

Wissensbasis	5

Wissensrepräsentation	5

zeitliche Anordnung	47

Ziel	13

zulässig	45

Zustandsraum	47

zyklisch	7

auf der linken Seite des Pfeils nur eine Bedingung

links nur eine Bedingung, rechts nichts

links nichts, rechts mind. eine Bedingung

Pfeil alleine ;-)

Mitschrift	Wissensbasierte Systeme

28.01.2005	Seite 39 von 50

Wissensbasierte Systeme

FH Ingolstadt; Mitschrift

FH Ingolstadt 2003

2003-10-09T00:02:54